package com.alex.algorithm.medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LongestSubStringWithoutRepeatingChar {

    public static void main(String[] args) {
        System.out.println(longestSubStringWithoutRepeatingChar("abcabcbb"));
        System.out.println(longestSubStringWithoutRepeatingChar("bbbbb"));
        System.out.println(longestSubStringWithoutRepeatingChar("pwwkew"));
    }

    public static int longestSubStringWithoutRepeatingChar(CharSequence sequence) {
        Map<Character,Boolean> charExist = new HashMap<>();
        List<Character> charWindow = new ArrayList<>();
        int res = 0;
        for (int i = 0 ; i < sequence.length(); ++i){
            char key = sequence.charAt(i);
            if (charExist.containsKey(key)) {
                int index = charWindow.indexOf(key);
                for (int j = 0; j < index; ++j) {
                    charExist.put(charWindow.get(j), false);
                }
                charWindow = charWindow.subList(index+1,charWindow.size());
                charWindow.add(key);
            }else {
                charWindow.add(key);
                if (charWindow.size() > res) {
                    res = charWindow.size();
                }
            }
            charExist.put(key, true);

        }
        return res;
    }

}
